//--------------------------------------------------
/**
 *
 *      Hand Gesture Recognition System
 *
 */
//--------------------------------------------------
/**
 * //HMM CLASS//
 * Librería de procesamiento de Modelos Ocultos de Marcov
 *
 * @author  Edwin Cobos & Cesar Murcia
 * @version HGR_v1.3
 *
 * Revisado: 18/11/11
 */
//--------------------------------------------------
//PACKAGE//
package hmm;
//IMPORT//
import HGR.Learning.Punto;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

//--------------------------------------------------
/**
 * HMM Class Integra los procesos de los Modelos Ocultos de Marcov
 */
public class Hmm
{
    //--------------------------------------------------
    /**
     * Secuencia de Observaciones O={S1,S2,S3,...}.
     */
    public static int[] O;

    /**
     * Probabilidad D usada para la convergencia de la reestimación
     */
    public static float D;

    public static int N = 3;
    public static int Angulo = 60;

    /**
     * @param args the command line arguments
     */

    //--------------------------------------------------
    /**
     * Proceso principal de HMM de acuerdo al árbol de procesos.
     * @param args
     */
    public static void main(String[] args)
    {
        /*int N=3;
	float[] Pi={0.333,0.333,0.333};
	String[] M={"1","2","3","4"};
	float[][] A={
        {0.333,0.333,0.333},
        {0.333,0.333,0.0},
        {0.5,0.0,0.5}};
        
	float[][] B={
            {1.0/M.length,1.0/M.length,1.0/M.length,1.0/M.length},
            {1.0/M.length,1.0/M.length,1.0/M.length,1.0/M.length},
            {1.0/M.length,1.0/M.length,1.0/M.length,1.0/M.length}};
        
	int[] Oj= {0,1,1,0,2,0,1,3,3,1};
	D = 1.0E-30;
        O = Oj;
        Model lambda0 = new Model(N, M, A, B, Pi);
        //System.out.println(lambda0.toString());
        Model lambda1 = BaumWelch(lambda0);
        System.out.println(lambda1.toString());*/

        //Inicialización        
                

        
    }

    public static Model Hmm_Learning(int[] Obs, Model lambda0)
    {
        O = Obs;
        D = Float.MIN_VALUE;
        //Model lambda0 = new Model(N, M, A, B, Pi);
        Model lambda1 = BaumWelch_learning(lambda0);

        return lambda1;
    }
    
    public static Model Hmm(int[] Obs, int States, int Angles)
    {
        N = States;
        Angulo = Angles;
        float[] Pi = new float[N];
        for(int i=0; i<Pi.length; i++)
            Pi[i] = 1.0f/N;

        String[] M = new String[360/Angulo];
        for(int i=0; i<M.length; i++)
            M[i] = String.valueOf(i*Angulo);

        float rnd =0.0f;
        float count =0;
        float[][] A = new float[N][N];
        /*for(int i=0; i<A.length; i++)
        {
            count =0.0f;
            for(int j=0; j<A[i].length; j++)
            {
                rnd = (float)Math.random();
                while(rnd<0 || rnd>100)
                    rnd = (float)Math.random();
                count += rnd;
                A[i][j] = rnd;
            }
            for(int j=0; j<A[i].length; j++)
            {
                A[i][j] = A[i][j] / count;
            }
        }*/
        for(int i=0; i<A.length; i++)
        {
            for(int j=0; j<A[i].length; j++)
            {
                A[i][j] = 1.0f/N;
            }
        }


        float[][] B = new float[N][M.length];
        for(int i=0; i<B.length; i++)
        {
            for(int j=0; j<B[i].length; j++)
            {
                B[i][j] = 1.0f/M.length;
            }
        }

        //O = Iniciar(Angulo, );
        O = Obs;
        D = Float.MIN_VALUE;

        Model lambda0 = new Model(N, M, A, B, Pi);
        //Model lambda1 = BaumWelch(lambda0);
        Model lambda1 = BaumWelch_learning(lambda0);
        //System.out.println(O);
        
        return lambda1;
    }

    //--------------------------------------------------
    /**
     * Inicializa la secuencia de observaciones desde archivo
     * @param Angulo Número de división de ángulos a cargar
     */
    public static Punto[] Iniciar(int Angulo, String type, String Dir)
    {
        ArrayList<String> filesHist = new ArrayList<String>();
        String[] gestos = {"AUM","DIS","ESC","ROT","TRA","X","Y","Z"};
        ListDir(Dir, filesHist, ".hist");

        int h,k;
        Punto[] Obs = new Punto[filesHist.size()];
        for(h=0;h<Obs.length;h++)
            Obs[h] = new Punto();
        
        // por cada observación
        for(h=0;h<filesHist.size();h++)
        {
            String filename = filesHist.get(h);
            String[] part = filename.split("_");
            String[] part2 = part[1].split("/");

            for(k=0; k< gestos.length; k++)
            {
                if(gestos[k].equals(part2[part2.length-1]))
                {
                    //Obs[h][0] = k;
                    Obs[h].g = k;
                    break;
                }
            }

            Obs[h].MaxiHist = ReadFile(type, String.valueOf(Angulo), filename);
            //Obs[h][1] = PMax(Hist);             
        }
        return Obs;
    }

    //--------------------------------------------------
    /**
     * Selecciona la observación Vk que máximiza la probabilidad B de la observación
     * @param Histogram Array con el histograma de la distribución de probabilidades de las observaciones
     * @return Id de la observación Vk que máximiza la probabilidad B de la observación
     */
    public static int PMax(float[] Histogram)
    {
        float Max=0.0f;
        int MaxId = 0;
        int i;
        //MAXIMO
        for(i=0; i<Histogram.length; i++)
        {
            if(Histogram[i]>Max)
            {
                Max=Histogram[i];                
                MaxId = i;
            }
        }

        //MEDIA
        /*for(i=0; i<Histogram.length; i++)
        {
            Max += Histogram[i];
        }
        Max = Max/Histogram.length;

        float diff = Float.MAX_VALUE;
        for(i=0; i<Histogram.length; i++)
        {            
            if(diff > Math.abs(Max - Histogram[i])){
                diff = Math.abs(Max - Histogram[i]);
                MaxId = i;
            }
        }*/

       /* float[] nH = Arrays.copyOf(Histogram, Histogram.length);

        Arrays.sort(nH);
        for(i=0; i<Histogram.length; i++)
        {
            if(nH[nH.length/2] == Histogram[i])
                MaxId = i;
        }
        //Maxid = (int)(Histogram.length/2)*/
        return MaxId;
    }

    //--------------------------------------------------
    /**
     * Lee los archivos y devuelve el histograma de ángulos
     * @param Type Tipo de histograma: SIFT o SURF
     * @param Angle Número de división de ángulos a cargar
     * @param filename Nombre del archivo
     * @return Array con el histograma de ángulos
     */
    public static int[] ReadFile(String Type, String Angle, String filename)
    {            
        int[] Salida = null;
        File archivo = null;
        //FileReader fr = null;
        InputStreamReader fr = null;
        BufferedReader br = null;
        String[] Angulos = {"10","15","30","45","60"};
        try
        {
            archivo = new File (filename);
            //fr = new FileReader (archivo);
            fr = new InputStreamReader(new FileInputStream(archivo), "UTF-8");
            br = new BufferedReader(fr);
            // Lectura del fichero
            String linea;
            String[] part;
            int l = 0;
            //Mientras halla lineas en el archivo
            while((linea=br.readLine())!=null)
            {
                part = linea.split("#");
                if(part.length > 1)
                {
                    if(part[1].equals(Type))
                    {
                        for(int Ang=0; Ang<Angulos.length; Ang++)
                        {
                            linea=br.readLine();
                            if(Angle.equals(Angulos[Ang]))
                            {
                                part = linea.split(" ");
                                Salida = new int[part.length];
                                for(int i=0; i<part.length; i++)
                                {
                                    Salida[i] = (Integer.parseInt(part[i]));
                                }
                                break;
                            }
                        }
                    }
                }

                l++;
            }
        }
        catch(Exception e)
        {
            e.printStackTrace();
        }
        finally
        {
            //Cerrar el Archivo
            try
            {
                if( null != fr )
                {
                    fr.close();
                }
            }
            catch(Exception e2)
            {
                e2.printStackTrace();
            }
        }
        return Salida;
    }

    //--------------------------------------------------
    /**
     * Realiza el proceso iterativo de Baum Welch para el aprendizaje del modelo
     * @param lambda Modelo inicial
     * @return Nuevo modelo donde coverge el proceso
     */
    public static Model BaumWelch_learning(Model lambda)
    {
        Model NewModel = lambda;

        ForwardBackward NewForwardBackward = ForwardBackwardAlgorithm(NewModel);
        reestimarModelo(NewModel, NewForwardBackward);
        //NewForwardBackward = ForwardBackwardAlgorithm(NewModel);
        
        return NewModel;
    }

    /**
     * Realiza el proceso iterativo de Baum Welch para el aprendizaje del modelo
     * @param lambda Modelo inicial
     * @return Nuevo modelo donde coverge el proceso
     */
    public static Model BaumWelch(Model lambda)
    {
        Model NewModel = lambda;//new Model( lambda.N, (String[])lambda.M.clone(), (float[][])lambda.A.clone(), (float[][])lambda.B.clone(), (float[])lambda.Pi.clone());

        int iteration;
	float oldProbability;
        ForwardBackward NewForwardBackward = ForwardBackwardAlgorithm(NewModel);
        iteration = 0;
        do
        {
	    iteration++;
	    oldProbability = NewForwardBackward.observationsProbability;
	    reestimarModelo(NewModel, NewForwardBackward);
	    NewForwardBackward = ForwardBackwardAlgorithm(NewModel);
            
	}
        while ((NewForwardBackward.observationsProbability - oldProbability) > D);
        
        //System.out.println(iteration);
        return NewModel;
    }

    //--------------------------------------------------
    /**
     * Realiza el Algoritmo de Forward-Backward
     * @param lambda Modelo Inicial
     * @return Resultado del algoritmo (alfa,beta,gamma,observationsProbability)
     */
    public static ForwardBackward ForwardBackwardAlgorithm(Model lambda )
    {
        ForwardBackward ForwardBackwardResult = new ForwardBackward();
        ForwardBackwardResult.alfa = calcularAlfa(lambda);
        ForwardBackwardResult.beta = calcularBeta(lambda);
        ForwardBackwardResult.gamma = calcularGamma(lambda, ForwardBackwardResult.alfa, ForwardBackwardResult.beta);
        ForwardBackwardResult.observationsProbability = CalcularProbabilidadObs(lambda, ForwardBackwardResult.alfa);

        return ForwardBackwardResult;
    }

    //--------------------------------------------------
    /**
     * Opera los valores de forward (alfa)
     * @param lambda Modelo Inicial
     * @return valores de Forward (alfa)
     */
    private static float[][] calcularAlfa(Model lambda)
    {
	float[][] Alfa;	
	float previousObsSum;
        float AlphaSum = 0;
	Alfa = new float[O.length][lambda.N];

	// Inicialización Eq. 19 (t=0)
        int i;
	for (i = 0; i < lambda.N; i++)
        {
	    Alfa[0][i] = lambda.Pi[i] * lambda.B[i][(int)O[0]];
            AlphaSum += lambda.Pi[i] * lambda.B[i][(int)O[0]];
	}

        // Escalamiento Eq. 91
        for (i = 0; i < lambda.N; i++)
        {
	    Alfa[0][i] = Alfa[0][i] / AlphaSum;
        }

	// Inducción Eq. 20
	// Por observación (1 < t < T)
	for (int t = 1; t < O.length; t++)
        {
	    // Por estado (1 < j < N)
            AlphaSum = 0;
	    for (int j = 0; j < lambda.N; j++)
            {
		previousObsSum = 0;
		for (i = 0; i < lambda.N; i++)
                {
		    previousObsSum += Alfa[t - 1][i] * lambda.A[i][j];
		}
		// observacion Actual
                Alfa[t][j] = previousObsSum * lambda.B[j][(int)O[t]];
		AlphaSum += Alfa[t][j];
	    }

            // Escalamiento Eq. 91
            for (int j = 0; j < lambda.N; j++)
            {
                Alfa[t][j] = Alfa[t][j] / AlphaSum;
            }
	}
	return Alfa;
    }
    
    //--------------------------------------------------
    /**
     * calcula la probabilidad de una secuencia de observaciones en un espacio logaritmico
     * @param lambda Modelo
     * @param Obs Secuencia de observaciones
     * @return valores de Forward (Phi)
     */
    public static double[][] CalcularProbabilidadO(Model lambda, int[]Obs)
    {
	double[][] Phi;
	double previousObsSum0;
        double previousObsSum1;
        double PhiSum = 0;
        double ObsSum = 0;
	Phi = new double[Obs.length][lambda.N];

	// Inicialización Eq. 19 (t=0)
        int i;
	for (i = 0; i < lambda.N; i++)
        {
            //Phi[0][i] = (lambda.Pi[i]* lambda.B[i][(int)Obs[0]]);
            Phi[0][i] = -(Math.log10(lambda.Pi[i]) + Math.log10(lambda.B[i][(int)Obs[0]]));

	}

	// Inducción Eq. 20
	// Por observación (1 < t < T)
	for (int t = 1; t < Obs.length; t++)
        {
	    // Por estado (1 < j < N)            
            ObsSum =0;
	    for (int j = 0; j < lambda.N; j++)
            {
		previousObsSum0 = 0;
                previousObsSum1 = 0;
		for (i = 0; i < lambda.N; i++)
                {
		    //previousObsSum0 += Phi[t - 1][i] * lambda.A[i][j];
                    previousObsSum0 += (Phi[t - 1][i]);
                    previousObsSum1 += -Math.log10(lambda.A[i][j]);
		}
                previousObsSum0 = (previousObsSum0 + previousObsSum1);
		// observacion Actual
                //Phi[t][j] = (double)(previousObsSum0 * lambda.B[j][(int)Obs[t]]);
                Phi[t][j] = (double)(previousObsSum0 +
                        -Math.log10(lambda.B[j][(int)Obs[t]]));
	    }
	}
       /*for (int j = 0; j < lambda.N; j++)
       {
           PhiSum = 0;
           for (int t = 0; t < Obs.length; t++)
           {
              PhiSum += Phi[t][j];
           }
           //System.out.print("");
           for (int t = 0; t < Obs.length; t++)
           {
              Phi[t][j] = Phi[t][j] / PhiSum;
           }
       }*/

       /* for (int t = 0; t < Obs.length; t++)
        {
	    // Por estado (1 < j < N)            
            PhiSum =0;
	    for (int j = 0; j < lambda.N; j++)
            {
               PhiSum += Phi[t][j];
            }
            
            for (int j = 0; j < lambda.N; j++)
            {
               Phi[t][j] = (Phi[t][j]/PhiSum);
            }
        }*/
	return Phi;
    }

    public static float CalcularProbabilidad(Model lambda, int[]Obs)
    {
        float[][] Alfa;
	float previousObsSum;
        float AlphaSum = 0;
	Alfa = new float[Obs.length][lambda.N];
        float[] Ct = new float[Obs.length];

        float Probability=0;

        int t,j;
        int i;

	// Inicialización Eq. 19 (t=0)        
	for (i = 0; i < lambda.N; i++)
        {
	    Alfa[0][i] = lambda.Pi[i] * lambda.B[i][(int)Obs[0]];
            AlphaSum += lambda.Pi[i] * lambda.B[i][(int)Obs[0]];
	}
        Ct[0] = 1.0f/AlphaSum;

        // Escalamiento Eq. 91
        for (i = 0; i < lambda.N; i++)
        {
	    //Alfa[0][i] = Alfa[0][i] / AlphaSum;
            Alfa[0][i] = Alfa[0][i] * Ct[0];
        }

	// Inducción Eq. 20
	// Por observación (1 < t < T)
	for (t = 1; t < Obs.length; t++)
        {
	    // Por estado (1 < j < N)
            AlphaSum = 0;
	    for (j = 0; j < lambda.N; j++)
            {
		previousObsSum = 0;
		for (i = 0; i < lambda.N; i++)
                {
		    previousObsSum += Alfa[t - 1][i] * lambda.A[i][j];
		}
		// observacion Actual
                Alfa[t][j] = previousObsSum * lambda.B[j][(int)Obs[t]];
		AlphaSum += Alfa[t][j];
	    }

            Ct[t] = 1.0f/AlphaSum;

            // Escalamiento Eq. 91
            for (j = 0; j < lambda.N; j++)
            {
                //Alfa[t][j] = Alfa[t][j] / AlphaSum;
                Alfa[t][j] = Alfa[t][j] * Ct[t];
            }
	}

        for (t = 0; t < Ct.length; t++)
        {
            Probability += Math.log10(Ct[t]);
        }
        

	//return Alfa;
        return Probability;//CalcularProbabilidadObs(lambda, Alfa);
    }

    public static float CalcularProbabilidadLog(Model lambda, int[]Obs)
    {
        float[][] Alfa;
        float previousObsSum0;
        float previousObsSum1;
        float PhiSum = 0;
        float ObsSum = 0;
        float AlphaSum = 0;
	Alfa = new float[Obs.length][lambda.N];

	// Inicialización Eq. 19 (t=0)
        int i;
	for (i = 0; i < lambda.N; i++)
        {
            Alfa[0][i] = (float)(-(Math.log10(lambda.Pi[i]) + Math.log10(lambda.B[i][(int)Obs[0]])));
	}

	// Inducción Eq. 20
	// Por observación (1 < t < T)
	for (int t = 1; t < Obs.length; t++)
        {
	    // Por estado (1 < j < N)
	    for (int j = 0; j < lambda.N; j++)
            {
		previousObsSum0 = 0;
                previousObsSum1 = 0;
		for (i = 0; i < lambda.N; i++)
                {
		    //previousObsSum0 += Phi[t - 1][i] * lambda.A[i][j];
                    previousObsSum0 += (Alfa[t - 1][i]);
                    previousObsSum1 += -Math.log10(lambda.A[i][j]);
		}
                previousObsSum0 = (previousObsSum0 + previousObsSum1);
		// observacion Actual
                //Phi[t][j] = (double)(previousObsSum0 * lambda.B[j][(int)Obs[t]]);
                Alfa[t][j] = (float)(previousObsSum0 +
                        -Math.log10(lambda.B[j][(int)Obs[t]]));
	    }
        }
	//return Alfa;
        return CalcularProbabilidadObs(lambda, Alfa);
    }

    //--------------------------------------------------
    /**
     * Opera los valores de backward (beta)
     * @param lambda Modelo Inicial
     * @return Valores de Backward (beta)
     */
    private static float[][] calcularBeta(Model lambda)
    {
	float[][] Beta;	
	float followingObsSum;
        float BetaSum = 0;
	Beta = new float[O.length][lambda.N];

	// Inicialización Eq. 24 (1 < i < N | t = T)
	for (int i = 0; i < lambda.N; i++)
        {
	    Beta[O.length - 1][i] = 1;
            BetaSum += Beta[O.length - 1][i];
	}

        // Escalamiento Eq. 94
        for (int i = 0; i < lambda.N; i++)
        {
            Beta[O.length - 1][i] = Beta[O.length - 1][i] / BetaSum;
        }

	// Inducción Eq. 25
	// Si solo hay una observacion, entonces no hay iteraciones.
	if (O.length > 1)
        {
	    // Por observación (t = T-1,T-2,...,1)
	    for (int t = O.length - 2; t >= 0; t--)
            {
		// Por estado (1 < i < N)
                BetaSum = 0;
		for (int i=0; i < lambda.N; i++)
                {
		    followingObsSum = 0;
		    for (int j = 0; j < lambda.N; j++)
                    {
			followingObsSum += lambda.A[i][j] * lambda.B[j][(int)O[t + 1]] * Beta[t + 1][j];
		    }
		    // Observación Actual
		    Beta[t][i] = followingObsSum;
                    BetaSum += Beta[t][i];
		}

                // Escalamiento Eq. 94
                for (int i=0; i < lambda.N; i++)
                {
                    Beta[t][i] = Beta[t][i] / BetaSum;
                }
	    }
	}
	return Beta;
    }

    //--------------------------------------------------
    /**
     * Opera los valores de Gamma
     * @param lambda Modelo Inicial
     * @param alfa Valores de Forward.
     * @param beta Valores de Backward.
     * @return Valores de Gamma.
     */
    private static float[][] calcularGamma(Model lambda, float[][] alfa, float[][] beta)
    {
	float[][] Gamma;
	float Denominator;
	Gamma = new float[O.length][lambda.N];

        // Eq. 27
	// Por Observación (1 < t < T)
	for (int t = 0; t < O.length; t++)
        {
	    // Probabilidad del estado en la observación actual.
            // (1 < i < N)
	    Denominator = 0;
	    for (int i = 0; i < lambda.N; i++)
            {
		Denominator += alfa[t][i] * beta[t][i];
	    }

            Denominator = Denominator == 0 ? D : Denominator;

	    // Por estado (1 < i < N)
	    for (int i = 0; i < lambda.N; i++)
            {
		Gamma[t][i] = (alfa[t][i] * beta[t][i]) / Denominator;
	    }
	}
	return Gamma;
    }

    //--------------------------------------------------
    /**
     * Calcula la probabilidad de la secuencia de observaciones, dado el modelo
     * @param lambda Modelo Inicial
     * @param alfa Valores de Forward.
     * @return Probabilidad de la secuencia de observaciones, dado el modelo.
     */
    public static float CalcularProbabilidadObs(Model lambda, float[][] alfa)
    {
	float ObseqProb;
	// Initialization
	ObseqProb = 0;
	// Por state
	for (int i = 0; i < lambda.N; i++)
        {
	    ObseqProb += alfa[alfa.length - 1][i];
	}
	return ObseqProb;
    }
    
    //--------------------------------------------------
    /**
     * Actualiza el Modelo con los valores re-estimados de sus parámetros
     * @param lambda Modelo actual donde se guardará la reestimación
     * @param NewforwardBackward Resultado del algoritmo de Forward-Backward de
     * acuerdo al modelo inicial y las observaciones
     */
    public static void reestimarModelo(Model lambda, ForwardBackward NewforwardBackward)
    {
	float[][][] Xi;
	float[][] gamma;
	float[] transFromSts;
	float[][] transBetweenSts;

	// Expected values
	Xi = calcularXi(lambda, NewforwardBackward);
	gamma = calcularNuevoGamma(lambda, Xi);
	transFromSts = calcularTransFromSts(lambda, gamma);
	transBetweenSts = calcularTransBetweenSts(lambda, Xi);
	// Re-estimation
	reestimarPi(lambda, gamma);
	reestimarA(lambda, transFromSts, transBetweenSts);
	reestimarB(lambda, gamma);
    }

    //--------------------------------------------------
    /**
     * Calcula la probabilidad de estar en un estado (Si) en el tiempo (t)
     * y en un estado (Sj) en el tiempo (t+1)     
     * @param lambda Modelo actual
     * @param NewForwardBackward Resultado del algoritmo de Forward-Backward de
     * acuerdo al modelo Actual y las observaciones
     * @return Array[][] que contiene probabilidad de estar en un estado (Si)
     * en el tiempo (t) y en un estado (Sj) en el tiempo (t+1)
     */
    private static float[][][] calcularXi(Model lambda, ForwardBackward NewForwardBackward)
    {
	float numerator;
	float denominator;
	float[][][] Xi;

	// Inicialización
	Xi = new float[O.length][lambda.N][lambda.N];

        // Eq. 37
	// Por observación
	for (int t = 0; t < O.length; t++)
        {
	    // Denominador
	    denominator = 0.0f;
	    // Por estado Si
	    for (int i = 0; i < lambda.N; i++)
            {
		// Por estado Sj
		for (int j = 0; j < lambda.N; j++)
                {
		    denominator += NewForwardBackward.alfa[t][i] * lambda.A[i][j]
                    *lambda.B[j][(int)O[t]] * NewForwardBackward.beta[t][j];
		}
	    }
            denominator = denominator == 0 ? D : denominator;

	    // Numerador
	    // Por estado Si
	    for (int i = 0; i < lambda.N; i++)
            {
		numerator = 0.0f;
		// Por estado Sj
		for (int j = 0; j < lambda.N; j++)
                {
		    // Numerador
		    numerator = NewForwardBackward.alfa[t][i] * lambda.A[i][j]
                    * lambda.B[j][O[t]]* NewForwardBackward.beta[t][j];

		    Xi[t][i][j] = numerator / denominator;
		}
	    }
	}
	return Xi;
    }

    //--------------------------------------------------
    /**
     * Calcular la probabilidad de estar en el estado (Si) en el tiempo (t)
     * @param lambda Modelo actual
     * @param xi Array[][] que contiene probabilidad de estar en un estado (Si)
     * en el tiempo (t) y en un estado (Sj) en el tiempo (t+1)
     * @return Probabilidad de estar en el estado (Si) en el tiempo (t)
     */
    private static float[][] calcularNuevoGamma(Model model, float[][][] xi)
    {
	float[][] NewGamma;

        //Eq. 38
	// Inicialización
	NewGamma = new float[O.length][model.N];

	// Por observación
	for (int t = 0; t < O.length; t++)
        {
	    // Por estado
	    for (int i = 0; i < model.N; i++)
            {
		// Por estado
		for (int j = 0; j < model.N; j++)
                {
		    NewGamma[t][i] += xi[t][i][j];
		}
	    }
	}
	return NewGamma;
    }

    //--------------------------------------------------
    /**
     * Calcula el número esperado de transiciones de cada estado
     * @param lambda Modelo actual
     * @param gamma Probabilidad de estar en el estado (Si) en el tiempo (t)
     * @return Número esperado de transiciones de cada estado
     */
    private static float[] calcularTransFromSts(Model lambda, float[][] gamma)
    {
	float[] TransFromSts;

        // Eq. 39a
	// Inicialización
	TransFromSts = new float[lambda.N];

        for (int t = 0; t < O.length - 1; t++)
        {
            for (int i = 0; i < lambda.N; i++)
            {
		TransFromSts[i] += gamma[t][i];
	    }
	}
	return TransFromSts;
    }

    //--------------------------------------------------
    /**
     * Calcular el número esperado de transiciones entre estados
     * @param lambda Modelo actual
     * @param xi Array[][] que contiene probabilidad de estar en un estado (Si)
     * en el tiempo (t) y en un estado (Sj) en el tiempo (t+1)
     * @return Número esperado de transiciones entre estados
     */
    private static float[][] calcularTransBetweenSts(Model lambda,float[][][] xi)
    {
	float[][] TransBetweenSts;

        //Eq. 39b
	// Inicialización
	TransBetweenSts = new float[lambda.N][lambda.N];

        for (int t = 0; t < O.length - 1; t++)
        {
            for (int i = 0; i < lambda.N; i++)
            {
                for (int j = 0; j < lambda.N; j++)
                {
		    TransBetweenSts[i][j] += xi[t][i][j];
		}
	    }
	}
	return TransBetweenSts;
    }

    //--------------------------------------------------
    /**
     * Actualiza el modelo con el valor reestimado de su distribucion de probabilidad inicial     *
     * @param lambda Modelo actual
     * @param gamma Probabilidad de estar en el estado (Si) en el tiempo (t)
     * @return Número esperado de transiciones de cada estado
     */
    private static void reestimarPi(Model lambda, float[][] gamma)
    {
	float[] reestimatedP;

        //Eq. 40a
	// Inicialización
	reestimatedP = new float[lambda.N];

	// Por estado
	for (int i = 0; i < lambda.N; i++)
        {
	    reestimatedP[i] = gamma[0][i];
	}
	// Actualiza el modelo
        lambda.Pi = reestimatedP;
    }

    //--------------------------------------------------
    /**
     * Actualiza el modelo con el valor reestimado de su distribucion de probabilidad de transiciones.
     * @param lambda Modelo actual
     * @param transFromSts Número esperado de transiciones de cada estado
     * @param transBetweenSts Número esperado de transiciones entre estados
     */
    private static void reestimarA(Model lambda, float[] transFromSts, float[][] transBetweenSts)
    {
	float[][] reestimatedA;

        // Eq. 40b
	// Inicialización
	reestimatedA = new float[lambda.N][lambda.N];
	// Por estado
	for (int i = 0; i < lambda.N; i++)
        {
	    // Por estado
            transFromSts[i] = transFromSts[i] == 0 ? D : transFromSts[i];
	    for (int j = 0; j < lambda.N; j++)
            {
		reestimatedA[i][j] = transBetweenSts[i][j] / transFromSts[i];
	    }
	}
	// Actualiza el modelo
	lambda.A = reestimatedA;
    }

    //--------------------------------------------------
    /**
     * Actualiza el modelo con el valor reestimado para su distribucion de probabilidad de las observaciones
     * @param lambda Modelo actual
     * @param gamma Probabilidad de estar en el estado (Si) en el tiempo (t)
     */
    private static void reestimarB(Model lambda, float[][] gamma)
    {
	float numerator;
	float denominator;
	float[][] reestimatedB;

        // Eq. 40c
	// Inicialización
	reestimatedB = new float[lambda.N][lambda.M.length];

	// Por estado
	for (int j = 0; j < lambda.N; j++)
        {
	    denominator = 0;
	    // Numero de veces que está en el estado j.
	    for (int t = 0; t < O.length; t++)
            {
		denominator += gamma[t][j];
	    }
            denominator = denominator == 0 ? 1.0f : denominator;

	    // Por cada M
	    for (int k = 0; k < lambda.M.length; k++)
            {
		numerator = 0.0f;
		// Numero veces en el estado k y observando el simbolo j
		for (int t = 0; t < O.length; t++)
                {
		    if (O[t] == k)
                    {
			numerator += gamma[t][j];
		    }
		}
		reestimatedB[j][k] = (numerator/denominator) == 0 ? 0.00001f : (numerator/denominator);
	    }
	}
	// Update lambda
	lambda.B = reestimatedB;
    }

     //--------------------------------------------------
    /**
     * Enlista los directorios y archivos de los videos
     * @param path Dirección de los archivos
     * @param dirs Lista donde se almacenan las direcciones
     * @param fileType Tipo de archivo que se enlista
     */
    public static void ListDir(String path, ArrayList<String> dirs, String fileType)
    {
        String t = path;
        File f = new File(t);
        if(f.isDirectory())
        {
            String[] fn = f.list();
            for(int i=0; i< fn.length; i++)
            {
                t = path+"/"+fn[i];
                ListDir(t, dirs,fileType);
            }
        }
        else if(f.isFile())
        {
            if(path.substring(path.length()-fileType.length(), path.length()).equals(fileType))
                dirs.add(path);
        }
    }
}
//--------------------------------------------------
//FIN
//--------------------------------------------------